1 Contenido de la clase
Búsqueda en árboles [00:00-01:41]
La búsqueda se representa sobre un árbol de búsqueda: el estado inicial es la raíz, los hijos corresponden a los sucesores (los estados a los que se llega aplicando los movimientos o acciones), y los nodos muestran los estados pero corresponden a los planes que alcanzan esos estados [00:26-00:34]. Rara vez se puede construir todo el árbol, porque el número de estados puede ser enorme (crece exponencialmente, del orden de 2^N para N elementos) [00:43-00:46, 21:27]. Propiedades del árbol: b es el factor de ramificación, m es la máxima profundidad, y las soluciones pueden estar en diferentes lugares [01:08-01:41].
Grafo de espacio de estados vs árbol de búsqueda [01:41-02:03]
Se distinguen dos grafos: el grafo de espacios de estados representa todos los estados posibles y sus conexiones; el grafo de búsqueda representa el progreso del algoritmo, mostrando qué estados se han visitado y expandido [01:41-01:54]. Cuando el espacio tiene infinitos estados o infinitas rutas, se hace necesario buscar [01:54-02:03].
Algoritmo general para buscar en un árbol [02:48-04:42]
Las ideas importantes del algoritmo general son la frontera (fringe), la expansión y la estrategia de exploración. La pregunta central es "¿qué nodo de la frontera explorar?" [03:23-03:31]. La expansión consiste en tomar un nodo de la frontera, ver si tiene hijos (sucesores) y escoger uno según la estrategia; si el nodo contiene el estado final (la meta) se llega a una solución; si no, se sigue explorando [02:51-03:19]. El algoritmo general necesita un problema, una estrategia y la función de solución; en este caso la respuesta es el camino que llega al objetivo, no el estado final [03:23-03:49].
Búsqueda en profundidad (DFS) [05:09-05:19, 20:00-20:20]
La búsqueda en profundidad extiende primero el nodo más profundo de la frontera [05:11-05:19]. Sus propiedades se evalúan con cuatro preguntas: ¿es completo? (¿garantiza encontrar una solución?), ¿es óptimo? (¿garantiza el camino de menor costo?), ¿complejidad en tiempo? y ¿complejidad en espacio? [20:10-20:20]. Usa poca memoria, pero no garantiza la solución óptima.
Búsqueda en anchura (BFS) [24:28-24:45]
La búsqueda en anchura extiende primero el nodo más superficial de la frontera, explorando por niveles [24:35-24:43]. Garantiza encontrar la solución más corta en número de pasos, pero consume mucha memoria porque debe guardar toda la frontera [22:06-22:12]. Se compara con DFS: ¿cuándo es mejor usar cada algoritmo? [24:47-24:55].
Búsqueda en profundidad iterativa [40:00-40:28, 42:22-42:53]
La búsqueda en profundidad iterativa combina las ventajas de DFS y BFS: se ejecuta DFS con límite 1 en profundidad, luego límite 2, luego límite 3, y así sucesivamente, visitando todos los nodos del mismo nivel en cada iteración [40:04-40:20, 42:22-42:35]. Mantiene la garantía de optimalidad de la búsqueda en anchura y la complejidad de la frontera de la búsqueda en profundidad, a cambio de revisar (retrabajar) nodos ya visitados en iteraciones anteriores [42:37-42:53].
Búsqueda de costo uniforme [44:20-46:41]
Cuando los costos de las aristas son distintos, la búsqueda de costo uniforme expande primero el nodo con el menor costo acumulado g(n) [44:20-44:34]. Procesa los nodos más baratos que la solución óptima: si C* es el costo de la solución óptima y ε es el costo mínimo de un arco, la profundidad "efectiva" es C*/ε, con complejidad de tiempo O(b^(C*/ε)) y espacio O(b^(C*/ε)) [45:15-45:49].
La estrategia única [62:24-63:07]
Todos los algoritmos pueden implementarse cambiando únicamente la estrategia en la frontera: una estrategia saca el nodo más superficial (BFS), otra el nodo más profundo (DFS), otra el de menor costo (costo uniforme) [62:39-63:01]. La recomendación es usar una cola de prioridad para la frontera.
Búsqueda informada y heurísticas [63:07-67:00]
Hasta ahora no se ha utilizado información del espacio de búsqueda. Una heurística es una función que estima qué tan cerca estamos de la meta, se diseña por problema (p. ej., la distancia entre dos ciudades) [64:38-64:45]. La búsqueda voraz expande el nodo que se ve más cerca, pero puede salir mal: el peor escenario es una búsqueda en profundidad mal guiada [66:25-66:45].
A* = costo uniforme + voraz [66:49-67:28]
El algoritmo A* ("el primer gran algoritmo del curso", con muchas aplicaciones en robótica) ordena la búsqueda de acuerdo con la suma f(n) = g(n) + h(n), donde g(n) es el costo utilizado por costo uniforme (costo real acumulado) y h(n) es el costo estimado por la búsqueda voraz (heurística) [66:53-67:22]. A* considera el costo real hasta el nodo más lo que falta (estimado) hasta la meta [67:16-67:28]. A* es óptimo siempre que la heurística sea admisible (que no sobreestime el costo real restante, h(n) ≤ h*(n)); la demostración formal se ve en la clase 5 [69:09-69:33].
Complementos y precisiones (para completar el tema)
- Costo uniforme = algoritmo de Dijkstra. Con costos positivos es exactamente el algoritmo de Dijkstra; es completo y óptimo si cada costo de arco es ≥ ε > 0.
- Optimalidad según el algoritmo: BFS es óptimo solo si todos los costos de paso son iguales; DFS no es óptimo; la profundidad iterativa sí (costos iguales); costo uniforme en general.
- Búsqueda bidireccional: expande a la vez desde el inicio y desde la meta y se detiene cuando las fronteras se cruzan; tiempo O(b^(d/2)), pero requiere generar predecesores y guarda dos fronteras.
- Memoria acotada: IDA* (profundización iterativa sobre el costo f) y RBFS (mejor alternativa) usan memoria lineal a cambio de revisitar nodos.
- A* completa y memoria: es completo si hay solución y los costos son ≥ ε > 0; mantiene todos los nodos en memoria (O(b^d)).
- Peor caso de la búsqueda voraz: exponencial, con memoria O(b^m); el "DFS mal guiado" es la intuición de una mala heurística.
2 Puntos destacados / Lo que hay que saber
3 Actividades y tareas pendientes
En esta clase no se dejó una tarea concreta con fecha de entrega; el profesor presentó la conferencia de algoritmos de búsqueda y adelantó que "para la otra vez" se verá más allá de la búsqueda clásica. Conviene repasar:
4 Dudas que podrían examinar
¿Qué es el factor de ramificación b y la máxima profundidad m?
Son propiedades del árbol de búsqueda: b es cuántos hijos tiene cada nodo y m la profundidad máxima; determinan el tamaño del árbol [01:08-01:41].
¿Qué es la frontera (fringe)?
Es la estructura de datos (cola de nodos pendientes) que decide qué nodo expandir a continuación según la estrategia [03:23-03:31, 62:39-63:01].
¿Por qué BFS garantiza el camino más corto pero gasta mucha memoria?
Porque explora por niveles (nodo más superficial) y debe guardar toda la frontera [24:35-24:43, 22:06-22:12].
¿Por qué DFS usa poca memoria pero no es óptimo?
Porque extiende siempre el nodo más profundo; puede encontrar una solución lejos del óptimo [05:11-05:19].
¿Qué ventaja tiene la profundidad iterativa?
Combina la optimalidad de BFS con la baja memoria de DFS, retrabajando nodos en cada iteración [40:04-40:28, 42:37-42:53].
¿Cómo funciona el costo uniforme y cuál es su complejidad?
Expande el nodo de menor costo acumulado g(n); profundidad efectiva C*/ε y complejidad O(b^(C*/ε)) en tiempo y espacio [44:20-44:34, 45:15-45:49].
¿Qué es una heurística?
Una función que estima qué tan cerca estamos de la meta, diseñada por problema (p. ej., distancia entre ciudades) [64:38-64:45].
¿Por qué A* es tan importante?
Es el primer gran algoritmo del curso, combina costo real y estimado f(n) = g(n) + h(n), y tiene muchas aplicaciones en robótica [66:53-67:22].
5 Sitios o recursos para visitar
Conceptos de BFS y DFS aplicados a la inteligencia artificial. · google.com
Función de evaluación f(n) = g(n) + h(n) y condiciones de optimalidad. · google.com
Expansión por costo acumulado y su complejidad O(b^(C*/ε)). · google.com
Revisión de los algoritmos de búsqueda clásicos en IA. · geeksforgeeks.org
Algoritmo que combina DFS con límite creciente de profundidad. · google.com
6 Glosario de términos
- Espacio de estados: conjunto de todas las configuraciones posibles de un problema.
- Estado inicial: configuración desde la cual comienza la búsqueda (raíz del árbol).
- Estado objetivo / meta: configuración deseada que se busca alcanzar.
- Sucesor: estado resultante de aplicar una acción o movimiento a un nodo.
- Nodo: representación de un estado en el árbol/grafo de búsqueda; corresponde a un plan.
- Frontera (fringe): conjunto de nodos pendientes de expandir.
- Expansión: proceso de generar los sucesores de un nodo.
- Factor de ramificación (b): número de hijos de cada nodo.
- Máxima profundidad (m): profundidad máxima del árbol de búsqueda.
- Completitud: propiedad de un algoritmo que garantiza encontrar una solución si existe.
- Optimalidad: propiedad de encontrar el camino de menor costo.
- Heurística h(n): función que estima qué tan cerca está un nodo de la meta.
- Búsqueda voraz: expande el nodo que se ve más cerca según la heurística.
- A*: algoritmo que ordena por f(n) = g(n) + h(n), combinando costo real y estimado; óptimo si la heurística es admisible.
- Costo uniforme (Dijkstra): expande el nodo de menor costo acumulado; completo y óptimo si los costos de arco son ≥ ε > 0.
- Búsqueda bidireccional: busca a la vez desde el inicio y desde la meta y para cuando las fronteras se cruzan; tiempo O(b^(d/2)).
- IDA* / RBFS: búsquedas de memoria lineal (revisitan nodos) que imitan a A* cuando el problema no cabe en memoria.
7 Mapa mental textual
- Problema de búsqueda
- Estado inicial (raíz) → acciones/sucesores → estado meta
- Árbol de búsqueda: b = ramificación, m = profundidad; rara vez se construye completo
- Grafo de espacios de estados vs grafo de búsqueda
- Algoritmo general
- Frontera (fringe) · Expansión · Estrategia de exploración
- ¿Qué nodo de la frontera explorar?
- Algoritmos de búsqueda no informada
- DFS: nodo más profundo → poca memoria, no óptimo
- BFS: nodo más superficial → óptimo en pasos, mucha memoria
- Profundidad iterativa: DFS con límite creciente → combina ventajas, retrabaja nodos
- Costo uniforme: menor costo g(n) → óptimo por costo, O(b^(C*/ε))
- Estrategia única: solo cambia la frontera (cola de prioridad)
- Búsqueda informada
- Heurística h(n): estima qué tan cerca de la meta (por problema)
- Voraz: nodo que se ve más cerca (riesgo: DFS mal guiado)
- A* = costo uniforme + voraz: f(n) = g(n) + h(n); ¿óptimo? (heurística admisible)
- Aplicaciones: robótica, pathfinding, planificación [66:53-67:22]